package com.yanceysong.codetop.s41_s50;


public class S47_Mid_31_下一个排列 {
    /**
     * LeetCode第31题：下一个排列（Next Permutation）
     * <a href="https://leetcode.cn/problems/next-permutation/">题目链接</a>
     * <p>
     * 定义：一个整数数组的一个「排列」是其所有成员以某种顺序排列形成的序列。
     * 要求：就地（in-place）将给定数组修改为它的「下一个字典序更大的排列」。
     * 如果不存在（当前排列已经是所有排列中字典序最大的），则重排为最小（升序）排列。
     * 只允许使用 O(1) 额外空间。
     * <p>
     * 示例：
     * 1. 输入：[1,2,3]  输出：[1,3,2]
     * 2. 输入：[3,2,1]  输出：[1,2,3] （因为当前已是最大排列）
     * 3. 输入：[1,1,5]  输出：[1,5,1]
     * 4. 输入：[1,3,2]  输出：[2,1,3]
     * 5. 输入：[2,3,1]  输出：[3,1,2]
     * <p>
     * 核心思路（经典三步）：
     * .Step1：从右向左找到第一个 nums[i] < nums[i+1] 的位置 i，称它为“下降转折点”或“pivot”。
     * 若没找到（整个序列单调不升），说明当前是最大排列，直接整体反转得到最小排列即可。
     * .Step2：再次从右向左找到第一个 > nums[pivot] 的元素 j（因为右侧是一个非升序序列，右端开始第一个大于 pivot 的即为紧邻的下一更大元素）。
     * 交换 pivot 与 j。
     * .Step3：反转 pivot 右侧的后缀（从 pivot+1 到末尾），使其成为最小的升序排列，从而得到“刚好比原序列大的下一个”。
     * <p>
     * 为什么正确？（关键洞察）
     * - 右侧后缀在 Step1 的定义下必然是非升序（从右到左单调不降）。
     * - 为了获得“最小的大于原排列”的结果，需要在 pivot 处增大最小幅度：选取右侧尾部第一个比它大的元素。
     * - 交换后右侧仍保持非升序；反转后得到最小的升序排列，使整体刚好提升一个最小单位。
     * <p>
     * 时间复杂度：O(n)  （最多两次线性扫描 + 一次反转）
     * 空间复杂度：O(1)  （原地修改）
     * <p>
     * 边界与特殊情况：
     * - 空数组或长度为1：无需操作。
     * - 全递减数组：直接整体反转。
     * - 存在重复元素：算法仍生效，因为比较与查找逻辑不依赖元素唯一性。
     * ------------------------------------------------------------
     * 核心三步：
     * . Step1 寻找 pivot：从右往左找到第一个 nums[i] < nums[i+1] 的位置 i。
     * . Step2 寻找并交换：再从右往左找到第一个 > nums[pivot] 的元素，交换它们。
     * . Step3 后缀反转：将 pivot 右侧区间整体反转，使其最小化（升序）。
     * ------------------------------------------------------------
     * 一、为什么 pivot 要“从右往左”找？
     * . - 右端排列变化最快；靠右的上升位置能实现最小的增量。
     * . - 找到最右的 nums[i] < nums[i+1]，说明 i+1..末尾是一个“非升序”后缀（从左到右降序），该后缀已经是该前缀下的最大排列。
     * . - 必须提升 nums[i]（pivot）这个位置的数值才能得到“下一个”更大的排列。
     * ------------------------------------------------------------
     * 二、为何从右向左找第一个 > pivot 的元素即可？
     * . - 后缀是非升序（逆序的最大排列），从右向左第一个大于 pivot 的元素是“刚好”比 pivot 大的最小元素。
     * . - 交换后保证整体增加幅度最小，再通过后缀反转将其调到最小形态，得到紧邻的下一个排列。
     * ------------------------------------------------------------
     * 三、后缀反转的意义？
     * . - 交换后后缀仍是非升序（因为只换了一个更大的 pivot 位置），反转后得到升序 → 当前前缀下的最小排列。
     * ------------------------------------------------------------
     * 四、若找不到 pivot（数组整体非升序，如 [5,4,3,2,1]）
     * . - 整体已经是所有排列的最大值，下一个排列不存在 → 直接反转为最小的升序排列。
     * ------------------------------------------------------------
     * 示例演化：nums = [1,2,7,4,3,1]
     * .      索引:     0 1 2 3 4 5
     * .      值:       1 2 7 4 3 1
     * . Step1：从右向左扫描上升对：
     * .   (3,1) 不上升；(4,3) 不上升；(7,4) 不上升；到 (2,7) 发现 2 < 7 → pivot=1，pivot值=2
     * . Step2：从右向左找第一个 >2 的元素：依次 1(不大于2)，3(>2) → nextLargerPos=4，值=3
     * .   交换后数组： [1,3,7,4,2,1]
     * . Step3：反转 pivot 右侧后缀（从 index=2 到末尾）
     * .   后缀原始： [7,4,2,1]（非升序） → 反转 → [1,2,4,7]
     * .   最终结果： [1,3,1,2,4,7]
     * <p>
     * . 每一步示意：
     * .   原始:      [1,2,7,4,3,1]
     * .               \_/      ← 右端连续下降区
     * .   找 pivot:  [1,2,7,4,3,1] pivot=2(索引1)
     * .   找更大:    [1,(2↔3),7,4,2,1] → [1,3,7,4,2,1]
     * .   反转后缀:  [1,3 | 7,4,2,1] → [1,3 | 1,2,4,7] → [1,3,1,2,4,7]
     * ------------------------------------------------------------
     * 另一个例子：nums = [3,2,1]（全降序）
     * . Step1：无 pivot（没有上升对）
     * . Step2：跳过
     * . Step3：整体反转 → [1,2,3]
     * ------------------------------------------------------------
     * 示例 pivot 选择对结果影响（局部对比）
     * . 数组: [1,4,3,2]
     * . 从右找上升： (3,2) 不，(4,3) 不，(1,4) 是 → pivot=0
     * 右侧第一个 >1 的是 2(末尾) → 交换得 [2,4,3,1] → 反转后缀 [4,3,1] → [1,3,4] → 最终 [2,1,3,4]
     * 若错误选择更左 pivot 会导致跳过更小增量，产生非“紧邻”排列。
     * ------------------------------------------------------------
     * Mermaid 流程图（文本表示）
     * . graph TD
     * .   A[从右向左扫描找到 pivot] --> B{pivot 是否存在?}
     * .   B -->|是| C[从右向左找到第一个 > pivot 的元素]
     * .   C --> D[交换 pivot 与 该元素]
     * .   D --> E[反转 pivot 右侧后缀]
     * .   E --> F[返回结果]
     * .   B -->|否| G[直接整体反转]
     * .   G --> F[返回结果]
     * ------------------------------------------------------------
     * 时间复杂度：O(n)（pivot 扫描 O(n) + 查找更大元素 O(n) + 反转 O(n)，但串行常数级）
     * 空间复杂度：O(1)
     */
    public void nextPermutation(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return; // 空或单元素数组直接返回
        }

        // Step1: 找到从右往左第一个出现 "上升" 的位置，记作 pivotPos
        // 该位置满足 nums[pivotPos] < nums[pivotPos + 1]
        // 若不存在这样的 pivotPos，说明整个数组是非升序（如 5,4,3,2,1），即当前排列为最大，后续直接整体反转即可。
        int pivotPos = nums.length - 2; // 从倒数第二个元素开始向左扫描
        while (pivotPos >= 0 && nums[pivotPos] >= nums[pivotPos + 1]) {
            pivotPos--; // 继续左移，直到找到一个严格上升的“转折点”或越界
        }

        // Step2: 若找到 pivotPos，则在其右侧（后缀是非升序区域）寻找第一个 "比 nums[pivotPos] 大" 的元素
        // 由于右侧后缀整体是从左到右非升序，从最右端向左扫描第一个大于 pivot 的元素就是“最小的更大值”
        if (pivotPos >= 0) {
            int nextLargerPos = nums.length - 1; // 从数组末尾开始
            while (nextLargerPos >= 0 && nums[pivotPos] >= nums[nextLargerPos]) {
                nextLargerPos--; // 向左移动，寻找严格大于 pivot 的值
            }
            swap(nums, pivotPos, nextLargerPos); // 交换以实现最小增量
        }
        // Step3: 将 pivotPos 右侧的后缀整体反转，使其从原本的非升序变为升序，得到最小排列后缀
        // 若 pivotPos == -1（未找到 pivot），此时直接反转整个数组，得到最小的字典序排列
        reverseSuffix(nums, pivotPos + 1); // 后缀转为最小升序形态
    }

    /**
     * 交换数组中两个下标的值
     */
    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    /**
     * 反转从 start 到数组末尾的后缀
     */
    private void reverseSuffix(int[] nums, int start) {
        int left = start, right = nums.length - 1;
        while (left < right) {
            swap(nums, left, right);
            left++;
            right--;
        }
    }

    /**
     * 工具方法：格式化数组为字符串
     */
    private static String arrayToString(int[] arr) {
        if (arr == null) return "null";
        StringBuilder sb = new StringBuilder("[");
        for (int i = 0; i < arr.length; i++) {
            sb.append(arr[i]);
            if (i < arr.length - 1) sb.append(',');
        }
        sb.append(']');
        return sb.toString();
    }

    /**
     * 验证：生成所有排列的方式太昂贵，这里通过与预期输出对比 + 若需要可追加多轮调用验证。
     */
    private static void runSingleTest(int[] input, int[] expected) {
        // 深拷贝输入用于输出展示（避免就地修改影响打印前的内容）
        int[] original = new int[input.length];
        System.arraycopy(input, 0, original, 0, input.length);
        S47_Mid_31_下一个排列 solver = new S47_Mid_31_下一个排列();
        System.out.println("原始: " + arrayToString(original));
        solver.nextPermutation(input);
        System.out.println("结果: " + arrayToString(input) + "  期望: " + arrayToString(expected));
        boolean ok = expected.length == input.length;
        for (int i = 0; ok && i < input.length; i++) {
            if (input[i] != expected[i]) {
                ok = false;
                break;
            }
        }
        System.out.println(ok ? "✓ 测试通过" : "✗ 测试失败");
        if (!ok) throw new AssertionError("结果与期望不符");
        System.out.println("--------------");
    }

    // 分场景测试方法（模仿环形链表类的结构化测试风格）
    private static void testAscendingBasic() { // 测试1
        System.out.println("--- 测试1: 基本上升序 [1,2,3] -> [1,3,2] ---");
        runSingleTest(new int[]{1, 2, 3}, new int[]{1, 3, 2});
    }

    private static void testMaxPermutationReset() { // 测试2
        System.out.println("--- 测试2: 最大排列 [3,2,1] -> 重置升序 [1,2,3] ---");
        runSingleTest(new int[]{3, 2, 1}, new int[]{1, 2, 3});
    }

    private static void testWithDuplicates() { // 测试3
        System.out.println("--- 测试3: 含重复元素 [1,1,5] -> [1,5,1] ---");
        runSingleTest(new int[]{1, 1, 5}, new int[]{1, 5, 1});
    }

    private static void testMiddlePivot() { // 测试4
        System.out.println("--- 测试4: pivot 在中间 [1,3,2] -> [2,1,3] ---");
        runSingleTest(new int[]{1, 3, 2}, new int[]{2, 1, 3});
    }

    private static void testLeftPivotLongSuffix() { // 测试5
        System.out.println("--- 测试5: pivot 靠左 + 长后缀 [1,2,7,4,3,1] -> [1,3,1,2,4,7] ---");
        runSingleTest(new int[]{1, 2, 7, 4, 3, 1}, new int[]{1, 3, 1, 2, 4, 7});
    }

    private static void testTwoElements() { // 测试6
        System.out.println("--- 测试6: 两元素 [2,1] -> [1,2] ---");
        runSingleTest(new int[]{2, 1}, new int[]{1, 2});
    }

    private static void testSingleElement() { // 测试7
        System.out.println("--- 测试7: 单元素 [42] -> [42] ---");
        runSingleTest(new int[]{42}, new int[]{42});
    }

    private static void testRepeatPivotLeftSide() { // 测试8
        System.out.println("--- 测试8: 多重复 + pivot 左侧 [2,2,3,3] -> [2,3,2,3] ---");
        runSingleTest(new int[]{2, 2, 3, 3}, new int[]{2, 3, 2, 3});
    }

    private static void testLongSuffixReverse() { // 测试9
        System.out.println("--- 测试9: 长后缀整体反转 [1,5,4,3,2] -> [2,1,3,4,5] ---");
        runSingleTest(new int[]{1, 5, 4, 3, 2}, new int[]{2, 1, 3, 4, 5});
    }

    private static void testAllEqual() { // 测试10
        System.out.println("--- 测试10: 全相等 [7,7,7] -> [7,7,7] ---");
        runSingleTest(new int[]{7, 7, 7}, new int[]{7, 7, 7});
    }

    private static void testMultiStepChain() { // 额外链式多次推进
        System.out.println("--- 额外: 多轮推进链式展示 (起始 [1,2,3]) ---");
        int[] chain = {1, 2, 3};
        S47_Mid_31_下一个排列 solver = new S47_Mid_31_下一个排列();
        System.out.println("起始: " + arrayToString(chain));
        for (int step = 1; step <= 6; step++) { // 3! = 6 次循环遍历所有排列
            solver.nextPermutation(chain);
            System.out.println("第 " + step + " 次 -> " + arrayToString(chain));
        }
        System.out.println("（再次继续将回到最小排列）");
        System.out.println("--------------");
    }

    public static void main(String[] args) {
        System.out.println("=== 下一个排列算法测试开始 ===\n");
        testAscendingBasic();
        testMaxPermutationReset();
        testWithDuplicates();
        testMiddlePivot();
        testLeftPivotLongSuffix();
        testTwoElements();
        testSingleElement();
        testRepeatPivotLeftSide();
        testLongSuffixReverse();
        testAllEqual();
        testMultiStepChain();
        System.out.println("=== 所有测试完成 ===");
    }
}
